/*
 * File:    eg_vision.c
 * Purpose: Implementation of Algorithm V
 */

/*
 Copyright 2009 James Youngquist, Colin Scott.

 This file is part of ElectroGladiator.  ElectroGladiator is free
 software: you can redistribute it and/or modify it under the terms
 of the GNU General Public License as published by  the Free
 Software Foundation, either version 3 of the License, or (at your
 option) any later version.

 You should have received a copy of the GNU General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stddef.h>
#include <math.h>

#include "eg_vision.h"

/**
 * Algorithm S finds visible line segments, players, rocks, and trigons for p.
 * Pre: p->visible_lines contains lines to cast shadows on.  For example,
 *      cull_invisible_lines() has been called on p, as is done right away.
 * @param p The player
 * @param map_lines
 */
void algorithm_s(const Map *m, Player *p) {
    // Find lines inside FOV and place into player's visible_lines.
    cull_invisible_lines(m, p);

    /* == Algorithm S ==
        *
        * S is for Shadow,
        * as suggested by Sean,
        * and works opposite to V
        * whose implementation went wrong.
        *
        * For each line in visible_lines
        *   - create 2 rays from line's end points to beyond the map's borders,
        *     and call them RL and RR for left and right, to make a quadrilateral
        *     of line, RL, RR, and RL/RR end points.
        *   - For each other_line in map_lines that isn't this line
        *       - Find intersection for RL and RR.
        *       - If there are two intersections, take out that section from
        *         other_line.
        *       - Otherwise cut off the portion of other_line that is inside the
        *         frustrum.
        */

    double max_length = max_line_length(m);
    Line *RL = NULL; // Left Ray
    Line *RR = NULL; // Right Ray
    Line *l = NULL; // line casting shadows
    Line *other_l = NULL; // line shadows cast upon
    Node *outer_cur = p->visible_lines.front; // node (line) on outer loop

    while (outer_cur) {
        l = (Line*) outer_cur->data; // convenience variable

        // Don't test boundary walls because they cast shadows on nothing.
        // Boundary walls are either horizontal or vertical and have an end
        // point on the map's extrema.
        if ((is_vertical(l) && (fnear(l->p1.x, 0) || fnear(l->p1.x, m->width)))
                || (fnear(slope(l), 0) && (fnear(l->p1.y, 0)
                                           || fnear(l->p1.y, m->height)))) {
            outer_cur = outer_cur-> next;
            continue;
        }

        Node *inner_cur = p->visible_lines.front; // node (Line) on inner loop

        Point *left = left_point(p, l); // left end point
        Point *right = right_point(p, l); // right end point
        double theta_l, theta_r; // angle of ray from player to end point

        if (!left || !right) {
            // couldn't determine handedness of end points so line must be end
            // on to the player.  It can't therefor cast any shadows because
            // Lines have no thickness
            outer_cur = outer_cur-> next;
            continue;
        }

        theta_l = angle_to_point(p->location, *left);
        theta_r = angle_to_point(p->location, *right);

        RL = make_ray(left, theta_l, max_length);
        RR = make_ray(right, theta_r, max_length);

        // TODO: REMOVE INVISIBLE PLAYERS AND ROCKS

        while (inner_cur) {
            // Don't compare l to itself
            if (inner_cur == outer_cur) {
                inner_cur = inner_cur->next;
                continue;
            }

            other_l = (Line*) inner_cur->data;

            // If other_line has no length, remove it from list.
            if (fnear(line_length(other_l), 0)) {
                Node *tmp = inner_cur;
                inner_cur = inner_cur->next;
                Line *invisiline = (Line*) ll_rm_node(&p->visible_lines, tmp);
                free_line(invisiline);
                continue; // so don't advance inner_cur twice
            }

            Point inter_l;
            Point inter_r;

            int has_left_inter = intersection(RL, other_l, &inter_l);
            int has_right_inter = intersection(RR, other_l, &inter_r);

            if (inside_quad(RL, RR, &other_l->p1) && inside_quad(RL, RR,
                    &other_l->p2)) {
                Node *tmp = inner_cur;
                inner_cur = inner_cur->next;
                Line *invisiline = (Line*) ll_rm_node(&p->visible_lines, tmp);
                free_line(invisiline);
                continue; // so don't advance inner_cur twice
            } else if (has_left_inter && has_right_inter) {
                // Remove middle obscured section by creating a new line from
                // the visible right segment, adding it to the list, and then
                // shifting original right end point to the left intersection.
                Point *other_right = right_point(p, other_l);
                inner_cur->next = new_node(new_line(inter_r.x, inter_r.y,
                                                    other_right->x, other_right->y), inner_cur->next);
                *other_right = inter_l;
            } else if (has_left_inter && inside_quad(RL, RR, right_point(p,
                       other_l))) {
                // cut off right end point at inter_l if the right end point is
                // inside the frustrum.
                *right_point(p, other_l) = inter_l;
            } else if (has_right_inter && inside_quad(RL, RR, left_point(p,
                       other_l))) {
                // cut off left end point at inter_r if the left end point is
                // inside the frustrum.
                *left_point(p, other_l) = inter_r;
            }
            // ELSE do nothing with this line

            // If the resulting line has no length, remove it from list.
            if (fnear(line_length(other_l), 0)) {
                Node *tmp = inner_cur;
                inner_cur = inner_cur->next;
                Line *invisiline = (Line*) ll_rm_node(&p->visible_lines, tmp);
                free_line(invisiline);
                continue; // so don't advance inner_cur twice
            }

            inner_cur = inner_cur->next;
        }

        // free memory
        free_line(RL);
        free_line(RR);

        // go to next line
        if (outer_cur)
            outer_cur = outer_cur->next;
    }

    // Create VTs for backwards compatibility
    outer_cur = p->visible_lines.front;
    while (outer_cur) {
        Line *l = (Line*) outer_cur->data;
        Trigon *VT = new_trigon(p->location, l->p1, l->p2);
        ll_push(&p->vision_triangles, VT);
        outer_cur = outer_cur->next;
    }

    // Use the VTs to find visible rocks and players
    find_visible_entities(m, p);

    return;
}

/**
 * Places into p->visible_players all players p can see
 * Pre: algorithm_s and cull_invisible_entities() have been run.
 * @param m Map from which to draw candidate players
 * @param p Player that wants to see
 */
void find_visible_entities(const Map *m, Player *p) {
    Player *player; // Player to consider
    Rock   *rock; // Rock to consider
    Node   *cur_tri; // Trigon to consider
    LL     vis_rocks; // Temp storage for potentially visible rocks
    LL     vis_players; // Temp storage for potentially visible players

    ll_init(&vis_rocks, ROCK);
    ll_init(&vis_players, PLAYER);

    // Makes copies of map's rock/player data so freeing it isn't an issue
    cull_invisible_entities(m, p, &vis_rocks, &vis_players);

    while ( (rock = (Rock*)ll_pop(&vis_rocks))) {
        for(cur_tri = ll_itr_first(&p->vision_triangles); cur_tri != NULL;
                cur_tri = ll_itr_next(cur_tri)) {
            if (inside_tri((Trigon*)cur_tri->data, &rock->location)) {
                ll_push(&p->visible_rocks, rock);
                rock = NULL; // so not freed later
                break;
            }
        }
        if (rock) {
        	free_rock(rock);
        }
    }

    while ( (player = (Player*)ll_pop(&vis_players))) {
        for(cur_tri = ll_itr_first(&p->vision_triangles); cur_tri != NULL;
                cur_tri = ll_itr_next(cur_tri)) {
            if (inside_tri((Trigon*)cur_tri->data, &player->location)) {
                ll_push(&p->visible_players, player);
                player = NULL; // so not freed later
                break;
            }
        }
        if (player) {
        	free_player(player);
        }
    }

}

/**
 * Adds to player's visible_segments only lines from the map that are visible,
 * i.e. in the convex hull defined by the player's FOV.  It also truncates
 * lines that are intersected by the player's FOV boundaries. This could
 * probably be named better but then the poem wouldn't work.
 */
void cull_invisible_lines(const Map *m, Player *p) {
    /* == Algorithm C ==
     *
     * C is for cull
     * no cattle involved
     * only poor lines
     * that didn't fit in the hull
     *
     * For each line in m->lines
     *   - If that line has end points inside player's FOV, or is intersected
     *     by the FOV boundaries, then add that line to p->visible_lines,
     *     truncating it as necessary to fit into FOV.
     */
    double max_length = max_line_length(m);
    Line *FR = make_ray(&p->location, p->bearing - M_PI_4, max_length);
    Line *FL = make_ray(&p->location, p->bearing + M_PI_4, max_length);
    Trigon t = { p->location, FR->p2, FL->p2 };

    int i = 0;

    for (i = 0; i < m->num_lines; i++) {
        Line *l = new_line(m->lines[i]->p1.x, m->lines[i]->p1.y,
                           m->lines[i]->p2.x, m->lines[i]->p2.y); // copy of map's line
        Point *left = left_point(p, l);
        Point *right = right_point(p, l);
        Point inter_l = { -1, -1 }; // poss intersection with left FOV boundary
        Point inter_r = { -1, -1 }; // poss intersection with right FOV boundary

        int has_inter_l = intersection(FL, l, &inter_l);
        int has_inter_r = intersection(FR, l, &inter_r);

        if (has_inter_l) { // truncate on left
            *left = inter_l;
        }
        if (has_inter_r) { // truncate on right
            *right = inter_r;
        }

        if ((has_inter_l || has_inter_r ||
                (inside_tri(&t, &l->p1) && inside_tri(&t, &l->p2)))
                && !fnear(line_length(l), 0)) {
            ll_push(&p->visible_lines, l);
        } else {
            free_line(l);
        }
    }

    // Free memory
    free_line(FR);
    free_line(FL);
}

/**
 * Adds to rocks and players only entities from the
 * map that are visible, i.e. in the convex hull defined by the player's FOV.
 * It also truncates lines that are intersected by the player's FOV boundaries.
 */
void cull_invisible_entities(const Map *m, Player *p, LL *players, LL *rocks) {
    /*
    * For each rock/player in m
    *   - If that entity is inside player's FOV, then add it to the
    *     the corresponding data structure.
    */
    double max_length = max_line_length(m);
    Line *FR = make_ray(&p->location, p->bearing - M_PI_4, max_length);
    Line *FL = make_ray(&p->location, p->bearing + M_PI_4, max_length);
    Trigon t = { p->location, FR->p2, FL->p2 };

    Node *cur_rock;

    for (cur_rock = ll_itr_first(&m->rocks); cur_rock != NULL;
            cur_rock = ll_itr_next(cur_rock)) {
        Rock *tmp = (Rock*) cur_rock->data;
        if (inside_tri(&t,&tmp->location)) {
            Rock *r = new_rock(tmp->location.x, tmp->location.y, tmp->bearing,
                               tmp->owner);
            ll_push(rocks, r);
        }
    }

    int i;
    for (i = 0; i < m->num_players; i++) {
        Player *tmp = m->players[i];
        if (inside_tri(&t, &tmp->location)) {
            Player *p = new_player(tmp->location.x, tmp->location.y,
                                   tmp->bearing); // copy of player
            ll_push(players, p);
        }
    }

    // Free memory
    free_line(FR);
    free_line(FL);
}

// Removes either right or left end points from a list.  If keep_other is non
// zero, then do not remove end points of other lines that are the same as
// the opposing end point we want to remove.  For example, the middle of three
// colinear points is both a left and right end point for the two lines starting
// at the outermost points and ending in the middle.  If keep_other is
// specified, then the middle point will not be removed, assuming it is in the
// list of points.
// *keep_func is the function that will return either the left or right end
// point.  The correct function pointer is given through macros RM_RIGHT/LEFT.
void remove_pts(Point* (*keep_func)(const Player*, Line*), Map *map, Player *p,
                LL *points, int keep_other) {
    Point *p_to_examine = NULL; // point under scrutiny
    LL good_list; // valid points to save
    int i = 0; // generic index
    int is_right = 0; // true if point was a left point

    ll_init(&good_list, POINT);

    // For the remaining points, (assuming remove right points, else invert)
    // if a point is a right point then remove it, UNLESS keep_other == 1.  In
    // this case only remove that point if it is not the left point of another
    // line.  This is done by popping each point, examining it, and saving it
    // to a temporary linked list if valid, then finally restoring valid points
    // to the original linked list.
    while ((p_to_examine = ll_pop(points))) {
        is_right = 0;
        for (i = 0; i < map->num_lines; i++) { // check against each line
            if (is_endpoint(p_to_examine, map->lines[i])) {
                Point *keep = (*keep_func)(p, map->lines[i]);
                if (keep && same_point(keep, p_to_examine) && keep_other) {
                    ll_push(&good_list, p_to_examine);
                    p_to_examine = NULL; // set NULL so point not included twice
                    break; // only need one positive hit for inclusion
                } else {
                    is_right = 1;
                }
            }
        }
        if (p_to_examine) {
            if (is_right) {
                free_point(p_to_examine);
                p_to_examine = NULL;
            } else {
                ll_push(&good_list, p_to_examine);
            }
        }
    }

    // copy back into original list
    while ((p_to_examine = ll_pop(&good_list))) {
        ll_push(points, p_to_examine);
    }
}

// Removes duplicate points from linked list of points, free memory used by
// those points.
void remove_duplicate_pts(LL *l) {
    Node *base = l->front;

    while (base) {

        //remove_dups(base);

        Node *cur = base; // node that skips
        Node *next = cur->next; // node being checked
        Point *p = (Point*) cur->data; // value to check against

        while (next) { // not at end of list
            if (same_point(p, (Point*) next->data)) {
                cur->next = next->next;
                eradicate_node(next);
                l->length--; // update parent linked list
                next = cur->next;
            } else {
                cur = next;
                next = next->next;
            }
        }

        base = base->next;
    }

    return;
}

/** Returns longest line needed to cover all points on a map */
double max_line_length(const Map *m) {
    double base = sqrt(m->width * m->width + m->height * m->height) + 2;
    return M_SQRT2 * base; // return hypotenuse of 45-90-45 triangle
}
